import collections
from typing import List

INT_MAX = 100


class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])

        # 计算当前情况对应状态
        stat0 = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    stat0 |= (1 << (i * n + j))

        # 计算每一个位置的反转的影响状态
        change_stat = []
        for i in range(m):
            for j in range(n):
                stat = (1 << (i * n + j))
                if i > 0:
                    stat |= (1 << (i * n + j - n))
                if i < m - 1:
                    stat |= (1 << (i * n + j + n))
                if j > 0:
                    stat |= (1 << (i * n + j - 1))
                if j < n - 1:
                    stat |= (1 << (i * n + j + 1))
                change_stat.append(stat)

        # 定义状态矩阵
        dp = [INT_MAX] * (1 << (m * n))
        dp[stat0] = 0

        # 广度优先搜索
        queue = collections.deque([stat0])
        while queue:
            stat1 = queue.popleft()
            v1 = dp[stat1]
            for stat2 in change_stat:
                stat3 = stat1 ^ stat2
                if v1 + 1 < dp[stat3]:
                    dp[stat3] = v1 + 1
                    queue.append(stat3)

        # 返回最优解
        return dp[0] if dp[0] != INT_MAX else -1


if __name__ == "__main__":
    print(Solution().minFlips(mat=[[0, 0], [0, 1]]))  # 3
    print(Solution().minFlips(mat=[[0]]))  # 0
    print(Solution().minFlips(mat=[[1, 1, 1], [1, 0, 1], [0, 0, 0]]))  # 6
    print(Solution().minFlips(mat=[[1, 0, 0], [1, 0, 0]]))  # -1
